package com.cong.hj;

//题目描述：
// 给定一个会议时间安排的数组，
// 每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],...] (si < ei)，
// 为避免会议冲突，同时要考虑充分利用会议室资源，
// 请你计算至少需要多少间会议室，才能满足这些会议安排。
//
//        示例 1:
//        输入: [[0, 13],[5, 10],[15, 20]]
//        输出: 2

import java.util.*;

public class Main {
    public int roomNumber(List<List<Integer>> timeTable) {
        if (timeTable == null) return 0;
        int len = timeTable.size();
        if (len == 0) return 0;

        timeTable.sort((tp_1, tp_2) -> {
            return tp_1.get(1).compareTo(tp_2.get(1));
        });
        System.out.println(": " + timeTable);

        List<List<List<Integer>>> rooms = new LinkedList<>();
        List<Integer>[] compatibleRoomsMap = new List[len];

        List<Integer> lastTimePeriod = null;
        int i = -1;
        for (List<Integer> timePeriod : timeTable) {
            i++;
//            List<List<Integer>> compatibleRoom = null;
            boolean compatible = true;
            boolean onlyNotCompatibleWithLast = false;
            List<Integer> onlyNotCompatibleWithLastRoomIndex = new LinkedList<>();

            for (List<List<Integer>> room : rooms) {
                for (List<Integer> roomTimePeriod : room) {
                    if (!compatible(roomTimePeriod, timePeriod)) {
                        // 说明和该room 不兼容
                        compatible = false;
                        if (lastTimePeriod != null && !(roomTimePeriod.get(0).equals(lastTimePeriod.get(0)) && roomTimePeriod.get(1).equals(lastTimePeriod.get(1)))) {
                            // room中出现了不兼容的timePeriod并且不是上一个 timePeriod
                            onlyNotCompatibleWithLast = false;
                        } else {
                            // 出现了不兼容, 并且就是和上一个timePeriod不兼容
                            onlyNotCompatibleWithLast = true;
                        }
                    }
                }
                // 和该room兼容
                // 则把该room加入到该timeTable[i] 对应的Map中
                if (compatible) {
                    if (compatibleRoomsMap[i] != null) {
                        compatibleRoomsMap[i].add(rooms.indexOf(room));
                    } else {
                        compatibleRoomsMap[i] = new LinkedList<>();
                        compatibleRoomsMap[i].add(rooms.indexOf(room));
                    }
                } else { // 和该room不兼容
                    // 查看是否之和上一个tp 不兼容, 并且上一个tp还有其他的兼容room
                    if (onlyNotCompatibleWithLast && compatibleRoomsMap[i - 1] != null && compatibleRoomsMap[i - 1].size() > 0) {
                        onlyNotCompatibleWithLastRoomIndex.add(rooms.indexOf(room)); //
                        onlyNotCompatibleWithLast = false;
                    } // 否则什么也不做
                    compatible = true;
                }
            }// 遍历完所有的room
            if (compatibleRoomsMap[i] != null && compatibleRoomsMap[i].size() > 0) { // 当前的tp有相容的room
                rooms.get(compatibleRoomsMap[i].get(0)).add(timePeriod);
                compatibleRoomsMap[i].remove(0);
            } else { // 该tp 没有相容的room
                if (onlyNotCompatibleWithLastRoomIndex.size() > 0) { // 该tp 有一些room只和上一个tp不相容
                    // 那就将上一个tp向后放
                    List<List<Integer>> room = rooms.get(onlyNotCompatibleWithLastRoomIndex.get(0));
                    room.remove(lastTimePeriod); // 从该房间移除上一个tp
                    rooms.get(compatibleRoomsMap[i - 1].remove(0)).add(lastTimePeriod); // 将上一个tp加入该tp的下一个兼容room

                    // 将这个tp加入这个room
                    rooms.get(onlyNotCompatibleWithLastRoomIndex.get(0)).add(timePeriod);
                } else { // 该 tp 也没有只和上一个tp不相容的room
                    // 新建一个room, 并将本tp加入该room
                    List<List<Integer>> newRoom = new LinkedList<>();
                    newRoom.add(timePeriod);
                    rooms.add(newRoom);
                }
            }
            lastTimePeriod = timePeriod;

        }
        return rooms.size();
    }

    public boolean compatible(List<Integer> timePeriod_1, List<Integer> timePeriod_2) {
        return timePeriod_2.get(0) >= timePeriod_1.get(1) || timePeriod_1.get(0) >= timePeriod_2.get(1);
    }
}
